Понятия со словосочетанием «кратчайший путь»
Зада́ча о кратча́йшем пути́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
Связанные понятия
Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо (в случае взвешенных графов) суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является NP-трудной и не может быть решена за полиномиальное время...
Рыба — название схемы расположения маршрутизаторов, при которой из-за разницы в числе хопов и неправильно выставленной метрики трафик направляется только по кратчайшему пути, даже если это вызовет перегрузку короткого пути при простаивающих каналах более длинного пути.
В данной статье рассматриваются две параллельные прямые на плоскости Для параллельных прямых , расположенных не в одной плоскости, смотрите Скрещивающиеся прямые#расстояние.Расстояние между двумя прямыми линиями на плоскости - это наименьшее расстояние между любыми двумя точками, лежащими на линии. Или между точкой лежащей на прямой с другой параллельной прямой. В случае пересекающихся линий, расстояние между ними равно нулю, потому что минимальное расстояние между ними равно нулю (в точке пересечения...
Подробнее: Расстояние между прямыми
В вычислительной геометрии и планировании движений роботов граф видимости — это граф взаимной видимости точек пространства, обычно для множества точек и преград на евклидовой плоскости. Любая вершина в графе представляет точку пространства, а любое ребро представляет прямую видимость между точками. То есть, если отрезок прямой, соединяющий две точки пространства, не проходит через какую-либо преграду, в графе будет нарисовано ребро. Если множество точек пространства лежит на прямой, их можно понимать...
Подробнее: Граф видимости
Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.
Середина отрезка — точка на заданном отрезке, находящаяся на равном расстоянии от обоих концов данного отрезка. Является центром масс как всего отрезка, так и его конечных точек.
Параллельные прямые (от греч. παράλληλος, буквально — идущий рядом) — в планиметрии прямые, которые не пересекаются, сколько бы их ни продолжали в обе стороны.
Теорема Харкорта — это формула в геометрии для площади треугольника как функции длин сторон и расстояний от вершин треугольника до произвольной прямой, касательной к вписанной в треугольник окружности.
Задача Наполеона — знаменитая задача построения с помощью циркуля. В этой задаче дана окружность и её центр. Задача состоит в делении окружности на четыре равных дуги с помощью только циркуля. Наполеон был известным любителем математики, но неизвестно, он ли придумал или решил эту задачу. Друг Наполеона итальянский математик Лоренцо Маскерони придумал при геометрических построениях ограничение на использование только циркуля (не использовать линейку). Но, фактически, задача выше является более простой...
В метрике теории графов выпуклым подграфом неориентированного графа G называется подграф, который включает любой кратчайший путь в G между любыми двумя вершинами. Таким образом, это аналогично определению выпуклого множества в геометрии — такое множество содержит отрезок, соединяющий любые две точки множества.
Подробнее: Выпуклый подграф
Теорема Лестера — утверждение в геометрии треугольника, согласно которому в любом разностороннем треугольнике две точки Ферма, центр девяти точек и центр описанной окружности лежат на одной окружности (окружности Лестера). Названа именем канадского математика Джун Лестер (June Lester).
Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём...
Маршрут (нем. Marschroute, от франц. marche — ход, движение вперёд и route — дорога, путь) — путь следования объекта, учитывающий направление движения относительно географических ориентиров или координат, с указанием начальной, конечной и промежуточных точек, в случае их наличия.
Алгоритм Уайлера — Атертона (Вейлера — Азертона, Weiler–Atherton) используется в компьютерной графике для клиппинга (нахождения области пересечения) отсекаемого многоугольника по отсекающему многоугольнику, также называемому окном. Отсекаемый и отсекающий многоугольники могут быть невыпуклыми. Алгоритм применим только для плоских фигур.
Остовное дерево графа состоит из минимального подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрам.
Граф многоугольников на окружности можно задать «чередующейся последовательностью». Такую последовательность можно получить разорвав окружность в произвольном месте и перечислив вершины многоугольников, идя вдоль окружности. Такая последовательность единственна.
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь (путь в неориентированном или ориентированном графе, который проходит все вершины графа ровно один раз) или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны.
Теорема о пяти окружностях утверждает, что, если дана цепочка из пяти окружностей с центрами на общей шестой окружности, при этом точки пересечения соседних окружностей в цепочке лежат на той же шестой окружности, то прямые, соединяющие вторые точки пересечения, образуют пентаграмму, вершины которой лежат на этих пяти окружностях.
Расстояние от точки до прямой на плоскости — это кратчайшее расстояние от точки до прямой в евклидовой геометрии. Расстояние равно длине отрезка, который соединяет точку с прямой и перпендикулярен прямой. Формула вычисления расстояния может быть получена и выражена несколькими способами.
Построение выпуклой оболочки методом «разделяй и властвуй» — алгоритм построения выпуклой оболочки.
Подробнее: Алгоритм Киркпатрика
Гиперциклы через заданную точку, имеющие одну и ту же касательную в этой точке, сходятся к орициклу по мере стремления расстояния к бесконечности.
Алгоритм Тарьяна — алгоритм поиска компонент сильной связности в орграфе, работающий за линейное время.
Касательная прямая к окружности в евклидовой геометрии на плоскости — прямая, которая имеет с окружностью ровно одну общую точку. Также можно определить касательную как предельное положение секущей, когда точки пересечения её с окружностью бесконечно сближаются. Касательные прямые к окружностям служат предметом рассмотрения ряда теорем и играют важную роль во многих геометрических построениях и доказательствах.
В геометрии конциклическими (или гомоциклическими) точками называют точки, находящиеся на одной окружности. Три точки на плоскости, не лежащие на одной прямой, всегда лежат на одной окружности, поэтому иногда термин «конциклические» прилагают только к наборам из 4 или более точек.
Подробнее: Конциклические точки
Резистивное расстояние между двумя вершинами простого связного графа G равно сопротивлению между двумя эквивалентными точками электрической цепи, построенной путём замены каждого ребра графа на сопротивление в 1 ом. Резистивные расстояния являются метрикой на графах.
В евклидовой геометрии описанный четырёхугольник — это выпуклый четырёхугольник, стороны которого являются касательными к одной окружности внутри четырёхугольника. Эта окружность называется вписанной в четырёхугольник. Описанные четырёхугольники являются частным случаем описанных многоугольников.
Алгоритм Данцига — алгоритм для нахождения кратчайших путей ко всем вершинам планарного направленного графа. Назван в честь американского математика Джорджа Данцига.
Алгоритм сжатия цветков (англ. Blossom algorithm) — это алгоритм в теории графов для построения наибольших паросочетаний на графах. Алгоритм разработал Джек Эдмондс в 1961 году и опубликовал в 1965 году. Если дан граф G=(V, E) общего вида, алгоритм находит паросочетание M такое, что каждая вершина из V инцидентна не более чем одному ребру из M и M максимально. Паросочетание строится путём итеративного улучшения начального пустого паросочетания вдоль увеличивающих путей графа. В отличие от двудольного...
Многоугольник видимости или область видимости для точки p на плоскости среди препятствий — это (возможно неограниченная) многоугольная область всех точек плоскости, видимых из точки p. Многоугольник видимости можно определить для видимости из отрезка или многоугольника. Многоугольники видимости полезны в робототехнике, компьютерных играх и для определения позиций объектов, например, для определеиня наилучшего расположения охраны в картинных галереях.
Ортодро́мия, ортодро́ма (от др.-греч. «ὀρθός» — «прямой» и «δρόμος» — «бег», «путь») в геометрии — кратчайшая линия между двумя точками на поверхности вращения, частный случай геодезической линии.
Внеописанный четырёхугольник — это выпуклый четырёхугольник, продолжения всех четырёх сторон которого являются касательными к окружности (вне четырёхугольника). Окружность называется вневписанной. Центр вневписанной окружности лежит на пересечении шести биссектрис. Это биссектрисы двух внутренних углов противоположных углов четырёхугольника, биссектрисы внешних углов двух других вершин, и биссектрисы внешних углов в точках пересечения продолжений противоположных сторон (смотрите рисунок справа, указанные...
Алгоритм Демукрона — алгоритм решения задачи топологической сортировки, то есть упорядочения вершин графа по их уровням для бесконтурного ориентированного графа. Уровни вершин графа можно рассматривать как длины максимальных путей от входов до этих вершин.
Задача о наибольшей пустой сфере — это задача нахождения гиперсферы наибольшего радиуса в d-мерном пространстве, внутренность которой не перекрывает какое-либо из заданных препятствий.
Подробнее: Наибольшая пустая сфера
Зада́ча Кобо́на о треуго́льниках — нерешённая задача комбинаторной геометрии, сформулированная Кодзабуро Фудзмурой (яп. 藤村幸三郎 фудзимура ко:дзабуро:), известным также как Кобон. В задаче спрашивается, каково максимальное число N(k) неперекрывающихся треугольников, стороны которых принадлежат конфигурации k прямых. Вариант задачи рассматривается в проективной плоскости, а не в евклидовой плоскости, и в этом случае требуется, чтобы треугольники не пересекались другими прямыми конфигурации.
В евклидовой геометрии
пересечение двух прямых может быть пустым множеством, точкой или прямой. Различение этих случаев и поиск точки пересечения используется, например, в компьютерной графике, при планировании движения и для обнаружения столкновений.
Расстояние Фреше — это мера сходства кривых, принимающая во внимание число и порядок точек вдоль кривых. Расстояние названо по имени французского математика Мориса Фреше.
Антипараллелограмм, или контрпараллелограмм, — плоский четырёхугольник, в котором каждые две противоположные стороны равны между собою, но не параллельны, в отличие от параллелограмма. Длинные противоположные стороны пересекаются между собою в точке, находящейся между их концами; пересекаются между собою и продолжения коротких сторон.
Совершенная (или грациозная) разметка рёбер графа — это вид разметки графа. Это разметка для простых графов (в простом графе никакие два различных ребра не соединяют те же самые две различные вершины, никакое ребро не соединяет вершину с ней же (нет петель) и граф связен). Совершенные разметки рёбер ввёл в своей статье С. Ло.
В теории графов стягивание ребра — это операция, которая удаляет ребро из графа, а до этого связанные ребром вершины сливаются в одну вершину. Стягивание ребра является фундаментальной операцией в теории о минорах графов. Отождествление вершин — другая форма этой операции с более слабыми ограничениями.
Срединный граф — граф, представляющий рёбра смежности внутри граней заданного планарного графа.
Лемма о трезубце или теорема трилистника, или лемма Мансиона (жарг. лемма о куриной лапке) — теорема в геометрии треугольника.
Поиск в ширину (англ. breadth-first search, BFS) — метод обхода графа и поиска пути в графе. Поиск в ширину является одним из неинформированных алгоритмов поиска.
Арбелос (греч. άρβυλος — сапожный нож) — плоская геометрическая фигура, образованная большим полукругом, из которого вырезаны два меньших, диаметры которых лежат на диаметре большого и разбивают его на две части. Точнее, пусть A, B и C — точки на одной прямой, тогда три полуокружности с диаметрами AB, BC и AC, расположенные по одну сторону от этой прямой, ограничивают арбелос.
Алгоритм Кируса — Бека (англ. Cyrus — Beck) — алгоритм отсечения отрезков произвольным выпуклым многоугольником.
Локсодрома или локсодромия (от греч. «loxodromie»: греч. «loxos» — «косой», «наклонный» и греч. «dromos» — «путь») — кривая на поверхности вращения, пересекающая все меридианы под постоянным углом, называемым локсодромическим путевым углом.
Чевиана — это отрезок в треугольнике, соединяющий вершину треугольника с точкой на противоположной стороне. Часто рассматриваются три таких отрезка, пересекающихся в одной точке, которые совместно называются чевианами. Название «чевиана» происходит от имени итальянского инженера Джованни Чевы, доказавшего известную теорему о чевианах, которая носит его имя. Медианы, биссектрисы и высоты в остроугольном треугольнике являются специальными случаями чевиан.